package Graph;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class DijkstraPriorityQueue {
    //迪克斯特拉 单源最短路径(起点只有一个)
    public static void main(String[] args) {
        Vertex v1 = new Vertex("v1");
        Vertex v2 = new Vertex("v2");
        Vertex v3 = new Vertex("v3");
        Vertex v4 = new Vertex("v4");
        Vertex v5 = new Vertex("v5");
        Vertex v6 = new Vertex("v6");
        v1.edges = List.of(new Edge(v2, 7),
                new Edge(v6, 14),
                new Edge(v3, 9)
        );
        v2.edges = List.of(new Edge(v4, 15)
        );

        v3.edges = List.of(new Edge(v6, 2),
                new Edge(v4, 11)
        );
        v6.edges = List.of(new Edge(v5, 9)
        );
        v4.edges = List.of(new Edge(v5, 6)
        );
        v5.edges = List.of();

        List<Vertex> graph = List.of(v1, v2, v3, v4, v5, v6);
        dijkstra(graph, v1);
    }

    private static void dijkstra(List<Vertex> graph, Vertex source) {
        //创建一个优先队列
        PriorityQueue<Vertex> queue = new PriorityQueue<Vertex>(Comparator.comparingInt(value -> value.dist));
        //遍历加入
        graph.forEach(queue::offer);

        source.dist = 0;
        while (!queue.isEmpty()) {
            //选取当前顶点
            Vertex curr = queue.peek();
            //更新当前顶点邻居的距离
            updateneighboursDist(curr, queue);
            curr.visited = true;
            //移除
            queue.poll();

        }
        graph.forEach(vertex -> {
            System.out.println(vertex.name + " " + vertex.dist + " " + (vertex.prev != null ? vertex.name : "null"));
        });

    }

    private static void updateneighboursDist(Vertex curr, PriorityQueue queue) {
        curr.edges.forEach(temp -> {
            Vertex vertex = temp.linked;//邻居节点
            if (!curr.visited) {
                int i = curr.dist + temp.weigth; //当前节点 加上边的权重
                if (vertex.dist > i) {  // 邻居节点的值 是否大于 当前节点加上边的权重
                    vertex.dist = i;  //如果大于就发现了更短的路径
                    vertex.prev = curr;
                    queue.offer(vertex);
                }
            }
        });

    }


}
